#include "../../include/Dict/EditDistance.h"
#include<vector>
using std::vector;
using std::min;
int editDistance(const std::string & s1, const std::string &s2)
{
    vector<int> vec(s1.size() + 1);
     int lefttop = 0;
     int flag = -1;
     for (int i = 0; i <= s1.size(); ++i) {
         vec[i] = i;
     }
     for (int j =1 ; j <= s2.size(); ++j) {
         lefttop = vec[0];
         vec[0] = j;
         for (int i = 1; i <= s1.size(); ++i) {
             flag = (!(s1[i - 1] == s2[j-1]));
             int tmp = vec[i];
             vec[i] = min(min(vec[i - 1] + 1, vec[i] + 1), lefttop+flag);
             lefttop = tmp;
         }
     }
     return vec[s1.size()];

}
